// https://leetcode.cn/problems/minimum-window-substring/submissions/558808372/

class Solution {
public:
    int c1[256] {}, c2[256] {};
    string minWindow(string s, string t) {
        int l = 0, r = 0;
        int mx = 0x3f3f3f3f;
        int a1 = 0, a2 = 0;

        int x = s.size(), y = t.size();

        // 如果没有覆盖，就移动r
        // 如果覆盖了，那么就移动l，知道没有覆盖为止
        // 注意在移动r之前和check之前，必须更新c1，否则我们撤销c1的操作
        
        set<char> mp;
        for (auto it : t) {
            c2[it]++;
            mp.insert(it);
        }

        while (r < x) {
            c1[s[r]]++;

            bool ok = true;
            for (auto it : mp) {
                if (c1[it] < c2[it]) {
                    ok = false;
                    break;
                }
            }
        
            if (ok) {
                if (r - l + 1 < mx) {
                    mx = r - l + 1;
                    a1 = l, a2 = r;
                }
                c1[s[l]]--;
                c1[s[r]]--; //undo the cnt
                l++;
            } else {
                r++;
            }
        }
        return mx == 0x3f3f3f3f ? "" : s.substr(a1, a2 - a1 + 1);
    }
};